package dp.路径;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 最小路劲和64.java
 * @createTime 2024年02月29日 17:40:00
 */
public class 最小路劲和64 {
	/*
    位置，移动方向（向右，向下）
    定义dp函数，dp(i,j)表示在位置i和j的时候，有最小值
    状态转移：
    dp[i][j]=min(dp[i-1][j]+num[i][j],dp[i][j-1]+num[j][j])
    baseCase:因为只能向右和向下
    dp[0][0]=num[0][0]
    两条边和为累加值
    其余初始化为最大值
     */
	public int minPathSum(int[][] grid) {
		int row = grid.length;
		int col = grid[0].length;
		int[][] dp = new int[row][col];
		dp[0][0] = grid[0][0];
		for (int i = 1; i < row; i++) {
			dp[i][0] = dp[i - 1][0] + grid[i][0];
		}

		for (int j = 1; j < col; j++) {
			dp[0][j] = dp[0][j - 1] + grid[0][j];
		}

		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
			}
		}
		return dp[row-1][col-1];
	}
}
